package com.tree.sort;

import java.util.Arrays;

/**
 * @ClassName com.tree.sort
 * Description: <类功能描述>. <br>
 * <p>
 * <使用说明>
 * </p>
 * @Author tree
 * @Date 3/6/24 12:22 AM
 * @Version 1.0
 */
public class HeapSort {

    // 主函数，用于测试排序算法
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array:");
        printArray(arr);

        sort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }


        // 堆排序主方法
        public static void sort(int[] arr) {
            // 获取数组长度
            int n = arr.length;

            // 从最后一个非叶子节点开始，向上构建最大堆
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(arr, n, i);
            }

            // 逐个将最大元素移到数组末尾，然后重新调整堆
            for (int i = n - 1; i > 0; i--) {
                // 将当前最大元素（堆顶元素）与末尾元素交换
                swap(arr, 0, i);
                // 重新调整堆，使其满足最大堆的性质
                heapify(arr, i, 0);
            }
        }

        // 将以i为根节点的子树调整为最大堆
        private static void heapify(int[] arr, int n, int i) {
            // 初始化最大值为根节点
            int largest = i;
            // 左孩子节点的索引
            int leftChild = 2 * i + 1;
            // 右孩子节点的索引
            int rightChild = 2 * i + 2;

            // 如果左孩子节点存在且大于根节点
            if (leftChild < n && arr[leftChild] > arr[largest]) {
                // 更新最大值为左孩子节点
                largest = leftChild;
            }

            // 如果右孩子节点存在且大于当前最大值
            if (rightChild < n && arr[rightChild] > arr[largest]) {
                // 更新最大值为右孩子节点
                largest = rightChild;
            }

            // 如果最大值不是根节点，则交换根节点和最大值，并继续调整受影响的子树
            if (largest != i) {
                swap(arr, i, largest);
                heapify(arr, n, largest);
            }
        }

        // 交换数组中索引i和j处的元素
        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }



        // 打印数组的辅助方法
        private static void printArray(int[] arr) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }


}
